package com.chaos.eurekaproducer.leetCode;

import com.chaos.eurekaproducer.basic.ListNode;

/**
 * @author liaopeng
 * @title: Offer22
 * @projectName eureka-producer
 * @description:
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
 *
 *
 *
 * 示例：
 * 给定一个链表: 1->2->3->4->5, 和 k = 2.
 * 返回链表 4->5.
 *
 * 思路：
 * 采用双指针，两个指针都从头开始，前指针先走k步，后指针再开始走，当前指针走到最后一个节点那么后指针就到了指定位置了
 * @date 2021/6/10上午11:21
 */
public class Offer22 {
    public static ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null){
            return null;
        }
        ListNode nodeBefore = head;
        ListNode nodeAfter = head;
        int i=1;
        while (i<=k){
            nodeBefore = nodeBefore.getNext();
            i++;
        }
        while (nodeBefore!=null){
            nodeBefore = nodeBefore.getNext();
            nodeAfter = nodeAfter.getNext();
        }
        return nodeAfter;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode4.setNext(listNode5);
        listNode3.setNext(listNode4);
        listNode2.setNext(listNode3);
        listNode1.setNext(listNode2);
        ListNode kthFromEnd = getKthFromEnd(listNode1, 2);
        System.out.println(kthFromEnd.getVal());
    }
}
